package com.jhy.review.day08;

/**
 * 2022年9月1日15:25:32
 * 荷兰国旗问题
 * < = > 放在不同的位置
 */
public class NetherlandsFlag {
    //    num代表的是判断的数
    public static int[] partition(int[] arr, int l, int r, int num) {
        int less = l - 1;
        int more = r + 1;
//        截止条件 下标刚刚到达的是more 就截止了
        while (l < more) {
//            如果aar[l]位置上面的数小于num 就左边范围下一个数和num交换，然后l++
            if (arr[l] < num) {
                swap(arr, ++less, l++);
            } else if (arr[l] > num) {
//                如果arr[l]>num的话 直接右边范围的上一个数做交换，l不变
                swap(arr, --more, l);
            } else {
                l++;
            }
        }
//       less-1是边界 more-1 也是边界 刚好是 这范围内都是相同的
        return new int[] {less + 1, more - 1};


    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 3, 4, 4, 2, 2, 5, 6};
        printArray(arr);
        int[] partition = partition(arr, 0, arr.length - 1, 4);
        System.out.println(partition[0]);
        System.out.println(partition[1]);
        printArray(arr);
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}
